/**
 * @file     countBits.js
 * @brief    [338. 比特位计数](https://leetcode.cn/problems/counting-bits/description/)
 * @author   Zhu
 * @date     2023-02-12 16:49
 */

/**
 * O(n logn)
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
    const ans = [];
    for (let i = 0; i <= n; i++) {
        ans[i] = count(i);
    }

    return ans;

    function count(i) {
        let sum = 0;
        while (i > 0) {
            if (i & (1 === 1)) sum++;
            i = i >> 1;
        }

        return sum;
    }
};

/**
 * 最高有效位
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
    const ans = [0];
    let span = 0;
    for (let i = 1; i <= n; i++) {
        if ((i & (i - 1)) === 0) {
            span = i;
        }
        ans[i] = ans[i - span] + 1;
    }

    return ans;
};

/**
 * 最低有效位
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
    const ans = [0];
    for (let i = 1; i <= n; i++) {
        ans[i] = ans[i >> 1] + (i & 1);
    }

    return ans;
};
